Kingdom of Heaven bercerita tentang seorang jurutera dan panglima perang yang hidup sebagai seorang tukang besi di sebuah perkampungan di Perancis. Lelaki ini dihantui oleh tindakan dosanya kerana bunuh isterinya akibat keguguran. Sekelompok kecil pasukan Perang Salib datang ke rumahnya, meminta dibuatkan ladam untuk kuda-kuda mereka, juga makanan dan tempat berteduh, Balian (Bloom) memenuhi permintaan mereka. Kemudian Balian mengetahui jika pemimpin Pasukan Salib ini, Godfrey of Ibelin (Neeson), adalah ayahnya sendiri. Ternyata Godfrey datang memang ada maksud tertentu, iaitu untuk menuntut kembali anaknya yang telah ditinggalkan, Balian, dan mengajaknya pulang ke tanah suci Jerusalem.

Pada awalnya, Balian menolak ajakan Godfrey, kerana dia merasa tidak memerlukan pengakuan dari Geodfrey, yang selama ini dia mampu hidup tanpa ayahnya itu. Geodfrey tidak mahu maksa Balian dan dia faham mengapa Balian seperti itu. Kemudian, pasukan itu pun bergegas bersiap untuk kembali ke Jerusalem. Sebelum rombongan itu pergi, salah seorang tentera Geodfrey berpesan jika Balian berubah fikiran, dia masih boleh menyusul. Tentera itu memberitahu jalan yang mana satu mereka ikuti.

Ketika itu, ada seorang paderi kampung mencuri dengar perbualan. Paderi itu berusaha meyakinkan Balian bahawa dalam situasi yang Balian alami saat ini, akan lebih baik jika Balian pergi bersama Geodfrey. Paderi itu meyakinkan Balian bahawa Jerusalem merupakan tempat untuk mencari keampunan. Seperti reaksinya terhadap Geodfrey, Balian juga tidak mengendah perkataan paderi itu. Namun, ketika si paderi itu mula berkata hal yang menyakitakan tentang isterinya, pemuda ini marah dan membunuh paderi itu. Keadaan berubah semakin parah bagi Balian, membunuh seorang paderi merupakan kesalahan yang sangat besar, paderi itu mungkin ada benarnya juga, tidak ada lagi tempat untuk Balian di kampung itu, akhirnya Balian pun memutuskan untuk menyusul ayahnya pergi ke Jerusalem dengan harapan boleh menebus dosa dan keampunan Tuhan untuk isteri dan dirinya sendiri.

Setelah mereka meninggalkan desa itu, para askar penjaga tempatan datang menemui pasukan Salib hendak menangkap Balian. Pasukan Salib Geodfrey enggan menyerahkan Balian dan terjadilah pertumpahan darah yang kemudian dimenangi pasukan Godfrey tetapi banyak antara mereka yang terbunuh dan Godfrey sendiri luka parah akibat terkena panah.

Di Jerusalem, Godfrey, ketika hampir menjelang ajal, melantik Balian sebagai seorang ksatria dan memerintahkan agar Balian setia kepada Raja Jerusalem dan melindungi rakyat. Lalu, Balian mengenali tokoh politik penting Jerusalem, iaitu Raja Baldwin IV (Norton), yang sakit sopak tetapi seorang yang bijak, pemimpin yang baik hati; Puteri Sybilla (Green), adik perempuan Raja Baldwin IV dan yang juga telah menarik hati Balian; Guy de Lusignan, suami Sybilla yang licik, dahagakan darah, dan tidak ramah.

Kemudian, Guy dan Raynald de Chatillon (Gleeson) dengan sadis membantai rombongan Muslim yang sedang melintas gurun. Dengan perasaan murka, Saladin berangkat ke Kerak, istana milik Guy, bersama pasukannya untuk menuntut balas. Balian bersama para perajuritnya segera berangkat dari Ibelin untuk memberi bantuan kepada pihak Kerak melawan serangan Saladin (Massoud) itu. Walaupun kalah dari segi jumlah tentera, Balian dan para prajuritnya tetap gagah berani berusaha menahan serangan pasukan Saladin untuk sementara waktu agar para penduduk desa di sekitar Kerak boleh lari bertahan ke dalam istana. Pertempuran itu berakhir cepat, Balian dan pasukannya ditawan, namun tak lama dilepaskan kembali oleh seorang jeneral Muslim sebagai balasan kemuliaan hati Balian yang dia pelajari lama sebelum pertempuran itu. Akhirnya, Raja Baldwin IV tiba bersama pasukannya dan berhasil memujuk Saladin untuk menangguhkan penyerangan, mencegah pertumpahan darah yang sia-sia dan berjanji akan menghukum Raynald.

Raja Baldwin akhirnya meninggal dan pemerintahannya diturunkan ke Sibylla lalu melantik suaminya, Guy, sebagai Raja baru Jerusalem. Guy, dengan bantuan Raynald, menyambung peperangan dengan Saladin dengan membunuh adik perempuan Saladin, juga beberapa warga Muslim dan utusan Saladin. Bersama pasukan Ksatria Templar, Guy keluar dari kota Jerusalem ke gurun pasir untuk menyerang Saladin, tanpa memikirkan pentingnya faktor persediaan makanan dan minuman. Akibatnya, pasukan Muslim dengan mudah mampu mengalahkan pasukan Salib Templar yang telah lemah dan kelelahan itu dan pertempuran itu dikenal sebagai Perang Hattin. Raja Guy dan Raynald ditangkap dan kemudian dihukum penggal oleh Saladin, yang kemudian bergerak bersama pasukannya ke Jerusalem yang cuma ada Balian sebagai pelindung bandar. Peperangan berlalu 3 hari dengan cepatnya, Balian menunjukkan kehebatan taktiknya dengan menjatuhkan menara-menara penyerang Saladin. Suatu ketika, salah satu bahagian dinding Jerusalem berjaya dirobohkan, tetapi pasukan Balian dengan gigih mampu menahan kekuatan Saladin.

Keesokan harinya, Saladin mengajak Balian berunding, dan akhirnya Balian pun setuju menyerahkan Jerusalem kepada Saladin setelah Saladin mengajukan syarat jaminan keselamatan penganut Kristian untuk menghantar mereka ke negeri Kristian.

Di bahagian akhir filem, Balian telah berada di rumah lamanya di Perancis. Seperti kejadian sebelumnya, ada sekelompok pasukan Salib menuju ke rumah itu, kali ini pasukan itu dipimpin oleh Raja England Richard I. Richard mengatakan pada Balian bahawa beliau memimpin pasukannya dalam Perang Salib baru untuk merebut kembali Jerusalem dari Saladin. Raja Richard juga mengatakan beliau sedang mencari Balian, yang dikenali sebagai pembela Jerusalem, untuk memintanya bergabung, tapi Balian hanya mengaku dia hanyalah seorang tukang besi dan menolak ajakan tersebut. Kemudian kelihatan Sibylla, berpakaian jubah bulu mewah, dan Balian serta Sibylla berkuda bersama setelah berhenti sejenak di kubur isteri Balian.

Filem berakhir dengan tulisan bahawa setelah bertahun-tahun berperang, Richard tetap tidak mampu merebut kembali Jerusalem, dan peperangan merebut Jerusalem terus berlanjut hingga tahun-tahun mendatang, dengan bunyi "hingga hari ini, keamanan di Negara Syurga masih kabur."